import java.util.Stack;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "()"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: "()[]{}"
 * 输出: true
 * 示例 3:
 * <p>
 * 输入: "(]"
 * 输出: false
 * 示例 4:
 * <p>
 * 输入: "([)]"
 * 输出: false
 * 示例 5:
 * <p>
 * 输入: "{[]}"
 * 输出: true
 */
class Solution {

    public static void main(String[] args) {
        //System.out.println(isValid("()[]{}"));
        //System.out.println(isValid("(]"));
        //System.out.println(isValid("([)]"));
        //System.out.println(isValid("{[]}"));
        System.out.println(isValid("[]()[()()][{}]()"));
    }

    public static boolean isMatch(char a, char b) {
        return switch (a) {
            case '(' -> b == ')';
            case '[' -> b == ']';
            case '{' -> b == '}';
            default -> false;
        };
    }

    /**
     * 用栈的思想
     *
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (stack.empty()) {
                if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
                    stack.push(s.charAt(i));
                } else {
                    return false;
                }
            } else {
                if (isMatch(stack.peek(), s.charAt(i))) {
                    stack.pop();
                } else {
                    stack.push(s.charAt(i));
                }
            }
        }
        return stack.empty();
    }

    /**
     * 回溯算法
     *
     * @param s
     * @return
     */
    public static boolean isValid2(String s) {
        if (s == null || s.length() == 0) return true;
        if (s.length() % 2 == 1) return false;
        if (s.charAt(0) == '(' || s.charAt(0) == '[' || s.charAt(0) == '{') {
            for (int y = s.length() - 1; y > 0; y--) {
                if (isMatch(s.charAt(0), s.charAt(y))) {
                    if (isValid(s.substring(1, y)) && isValid(s.substring(y + 1))) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

}